package com.yehangtech.algorithm.算法基础篇.第一讲m基础算法._2_归并排序;

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 788. 逆序对的数量
 * 给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。
 * <p>
 * 逆序对的定义如下：对于数列的第 i个和第 j个元素，如果满足 i<j且 a[i]>a[j]，则其为一个逆序对；否则不是。
 * <p>
 * 输入格式
 * 第一行包含整数 n，表示数列的长度。
 * <p>
 * 第二行包含 n个整数，表示整个数列。
 * <p>
 * 输出格式
 * 输出一个整数，表示逆序对的个数。
 * <p>
 * 数据范围
 * 1≤n≤100000，数列中的元素的取值范围 [1,10^9]。
 * <p>
 * 输入样例：
 * 6
 * 2 3 4 5 6 1
 * 输出样例：
 * 5
 */
public class 逆序对的数量 {
    static long res = 0;
    static List<Integer> tempList = new ArrayList<>();

    static void mergeSort(List<Integer> list, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + right >> 1;
        mergeSort(list, left, mid);
        mergeSort(list, mid + 1, right);
        int i = left;
        int j = mid + 1;
        while (i <= mid && j <= right) {
            Integer v1 = list.get(i);
            Integer v2 = list.get(j);
            if (v1 <= v2) {
                tempList.add(v1);
                i++;
            } else {
                tempList.add(v2);
                j++;
                res += mid - i + 1;//这里是左区间元素个数
            }
        }
        while (i <= mid) {
            tempList.add(list.get(i++));
        }
        while (j <= right) {
            tempList.add(list.get(j++));
        }
        int k = left;
        for (Integer n : tempList) {
            list.set(k, n);
            k++;
        }
        tempList.clear();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(sc.nextInt());
        }
        mergeSort(list, 0, n - 1);
        System.out.println(res);
    }
}
